import org.w3c.dom.Node;

/**
 * 平衡二叉树：也叫二叉搜索树（AVL树），可以保证查询效率最高
 * 是一棵空树或者左右两个子树的高度差不会超过1，而且两颗子树都是AVL树
 * 常见的实现方法有红黑树，AVL，替罪羊树，Treap,伸展树
 * 通过左旋或者右旋实现平衡
 */
public class AVLTreeDemo {

    public static void main(String[] args) {
        int[] arr = {10,11,7,6,8,9};
    }

}
//创建一个AVLtree
class AVLTree{
    private Node root;


    public Node getRoot() {
        return root;
    }

    //查找要删除的节点
    public Node search(int value){
        if (root ==null){
            return null;
        }else {
            return  root.search(value);
        }
    }
    //查找父节点
    public Node searchParent(int value){
        if (root ==null){
            return  null;
        }else{
            return root.searchParent(value);
        }
    }
    public int delRightTreeMin(Node node){
        Node target = node;
        while (target.left!=null){
            target = target.left;
        }
        delNode(target.value);
        return target.value;
    }
    public void  delNode(int value){
        if (root==null){
            return;
        }else {
            Node targetNode = search(value);
            if (targetNode ==null){
                return;
            }
            if (root.left ==null&&root.right ==null){
                root =null;
                return;
            }
            Node parent = searchParent(value);
            if (targetNode.left ==null && targetNode.right ==null){
                if (parent.left !=null &&parent.left.value ==null){
                    parent.left =null;
                }else if (parent.right !=null &&parent.right.value ==null){
                    parent.right =null;
                }
            }else if (targetNode.left !=null && targetNode.right !=null){
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            }else {
                if (targetNode.left !=null){
                    if (parent !=null){
                        if (parent.left.value ==value){
                            parent.left = targetNode.left;
                        }else {
                            parent.right = targetNode.left;
                        }
                    }else {
                        root = targetNode.left;
                    }
                }else {
                    if (parent !=null){
                        if (parent.left.value ==value){
                            parent.left = targetNode.right;
                        }else {
                            parent.right = targetNode.right
                        }
                    }else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }


}

class  Node{
    int value;
    Node left;
    Node right;
    public  Node(int value){
        this.value = value;
    }
    public  int leftHeight(){
        if (left == null){
            return 0;
        }
        return left.height();
    }
    public  int rightHeight(){
        if (right == null){
            return 0;
        }
        return right.height();
    }

    public int height(){
        return Math.max(left==null?0:left.height(),right ==null?0:right.height())+1;
    }

    //左旋
    private void leftRotate(){
        Node newNode = new Node(value);
        newNode.left = left;
        newNode.right = right.left;
        value = right.value;
        right = right.right;
        left= newNode;
    }
    private void rightRotate(){
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right= newNode;
    }

    public Node search(int value){
        if (value ==this.value){
            return this;
        }else if(value<this.value){
            if (this.left ==null){
                return null;
            }
            return this.left.search(value);
        }else {
            if (this.right ==null){
                return null;
            }
            return this.right.search(value);
        }
    }

    public Node searchParent(int value){
        if ((this.left !=null&&this.left.value ==value)|| (this.right !=null && this.right.value ==value)){
            return this;
        }else {
            if (value <this.value && this.left!=null){
                return this.left.searchParent(value);
            }else if (value >=this.value&& this.right!=null){
                return  this.right.searchParent(value);
            }else {
                return null;
            }
        }
    }
}
